P6585 中子衰变 题解

我们对nn的奇偶进行分类讨论:

nn是偶数,我们选择后手。对于对手每次操作,我们操作其对称的位置,将其转变为与对手操作相同的粒子。容易证得这样的操作一定合法。

nn是奇数,我们可以尝试先操作最中间的位置,然后使用和上面类似的对称策略。但是由于如果全部中子最后变成了同种粒子,那么后手获胜。这条规则,这个策略并不成立。

换一个思路,我们选择后手。我们的操作策略要保证,每次我方操作后,局面状态满足一个循环不变式:

存在一个mn12m\le\frac{n-1}{2}使得,前mm个粒子和后mm个粒子相反对称,且中间剩余的一段除某一个端点没被操作外,其他部分都被操作成了相同的粒子。其中,相反对称的定义是:对于任意imi\le m,左起第ii个粒子和右起第ii个粒子要么都没被操作过,要么电性相反。

例如,以下情况都是满足条件的:

1 1 0 0 0 0 0 -1 -1
0 -1 0 1 1 0 0 1 0
0 1 1 1 1 1 1 1 1

(三个例子中mm分别可以取4,3,04,3,0

注意初始状态也是满足这个条件的,mmn12\frac{n-1}{2}即可。

我们可以采取以下策略维护这个循环不变式:

选择后手,对于对手每次操作,我们都操作其对称的位置,将其转变为与对手操作相反的粒子。但是有两种例外情况,可能导致我们的操作不合法:

  • 对手操作了中间一段剩下的那个端点。(例如在上面的第二行例子中,对手将第六格变成11)。由于我们保证左右两侧是相反对称的,那么与中间一段相邻的两个粒子中,必然有一个是可操作的。我们把这个格子操作成和中间一段相同的粒子(接上面的例子,把第七格变成11),易发现这样操作后循环不变式仍然满足,且mm的值减少了11。特殊地,如果mm已经是00,对手这样操作后必然导致所有粒子相同,根据规则后手胜。

  • 对手操作了中间一段剩下的那个端点相邻的一个点,且与中段的电性相同(例如在上面的第二行例子中,对手将第七格变成11)。此时我们只需要把那个端点操作成相同的粒子即可(接上面的例子,把第六格变成11)。循环不变式仍然成立,且mm的值减少了11

如果我们一直维护了这个循环不变式,对于对手的每一个合法操作我们都有一个对应的合法操作,显然后手必胜。